/**
 * Represents a partition of a graph
 */
public class GraphPartition {
    final private int NOT_IN_USE = -1; //Indicates an element of the a_array is not in use anymore, when two elements are merged then the one with the largest index is not used anymore
    private int _aArray[]; 
    private Matrix _eMatrix; 
    private Edge _edgeArray[]; 
    private CommunityCollection _communityCollection;
    private int _numEdges;
    private int _numVertices;
    private Graph _baseGraph;
    
    /**
     * Constructs a partition from a graph with each vertex being its own community
     * @param graph the underlying graph which is partitioned 
     */
    public GraphPartition(Graph graph)
    {
        int degree_array[] = graph.getAdjacencyMatrix().getDegArray();
        Edge graph_edge_array[] = graph.getEdgeArray();
        int i;
        
        _numEdges = graph.getEdgeCount();
        _numVertices = graph.getVertexCount();
        
        //Sets the partition to be such that each vertex is its own community,
        //this is the initial partition
        
        //Build e matrix from adjacency matrix
        //Definition of e-matrix in the CNM algo paper: http://arxiv.org/abs/cond-mat/0408187
        //In the initial case that each vertex is its own community,
        //the e-matrix is just like the adjacency matrix, but divided
        //by 2m, where m = # of edges.
        //I left out the factor of 2m so as to avoid numerical precision problems which would compound if we leave this factor in
        //The factor is still used in the getModularity method
        _eMatrix = new Matrix(graph.getAdjacencyMatrix());
        
        //Build a-array from degree matrix
        //Definition of a-array in the CNM algo paper: http://arxiv.org/abs/cond-mat/0408187
        //Again if we leave out the 2m factor, the a-array is identical
        //to the degree array in the case of each vertex being its own community
        //So this just copies the degree array
        _aArray = new int[degree_array.length];
        for (i=0; i < degree_array.length; i++)
        {
            _aArray[i] = degree_array[i];
        }
        
        //Also duplicate the edge array
        _edgeArray = new Edge[graph_edge_array.length];
        for (i=0; i < graph_edge_array.length; i++)
        {
            _edgeArray[i] = new Edge(graph_edge_array[i]);
        }
        
        //initialize the community collection, the indexing here starts at 1
        //to conform with the adjacency and e-matrix indexing
        _communityCollection = new CommunityCollection(graph.getVertexCount());
        
        _baseGraph = graph;
    }
    
    /**
     * @return  the graph which is partitioned
     */
    public Graph getGraph()
    {
        return _baseGraph;
    }
    
    /**
     * Merges two communities of the partition together.
     * The merged communities are those at the ends of the edge given as a parameter.
     * @param e The communities at the ends of this edge will be merged 
     */
    public void mergeCommunities(Edge e)
    {
        int smaller_index, larger_index;
        int index1 = e.firstEnd, index2 = e.secondEnd;
        
        if (index1 < index2) { smaller_index = index1; larger_index = index2; }
        else if (index2 < index1) { smaller_index = index2; larger_index = index1; }
        else { throw new IllegalArgumentException("Indices to merge must be different"); }
            
        //Change e-matrix (add rows and columns), implement as method of Matrix which adds rows and columns together
        _eMatrix.mergeRowsColsBySumming(e.firstEnd, e.secondEnd);
        
        //Change a-array (just add the elements)
        _aArray[smaller_index] += _aArray[larger_index];
        _aArray[larger_index] = NOT_IN_USE;
        
        //Change community collection (use the attach method)
        _communityCollection.mergeCommunities(index1, index2);
        
        //Change edge_array (to reflect that the community numbers changed)
        for (Edge curr_edge : _edgeArray)
        {
            if (curr_edge.firstEnd == larger_index) curr_edge.firstEnd = smaller_index;
            if (curr_edge.secondEnd == larger_index) curr_edge.secondEnd = smaller_index;
        }
    }
    
    /**
     * Returns the array of edges of the partition
     * This is different than that of the graph, as the ends
     * are communities and not simply vertices. 
     * Thus the index of the ends corresponds to communities
     * @return the edge array as specified
     */
    public Edge[] getEdgeArray()
    {
        return _edgeArray;
    }
    
    /**
     * Returns the collection of communities in the partition
     * @return the collection of communities in the partition
     */
    public CommunityCollection getCommunityCollection()
    {
        _communityCollection.setModularity(this.getModularity());
        return _communityCollection;
    }
    
    //It may be better to change it so the a_array and e-matrix do have the factors of 1/2m, bcs a_i is squared, so neglecting that factor changes the result, a quick fix I did now is to divide by 2m in this function.
    //OTOH if we keep the factor in the a_array we have an error and errors compound
    /**
     * @return the modularity value of the partition
     */
    public double getModularity()
    {
        //Uses the formula in the CNM algo paper, but again, without the 2m factors
        //So it is a sum over i of e_ii - (a_i)^2
        double modularity=0;
        double temp;
        
        for(int i=0;i<_numVertices;i++)
        {
            if (_aArray[i] != NOT_IN_USE)
            {
                temp = ((double)_aArray[i]*_aArray[i])/(2 * (double)_numEdges);
                modularity += (double)_eMatrix.element[i][i] - temp;
                
                assert _eMatrix.element[i][i] != _eMatrix.NOT_IN_USE;
            }
            else
            {
                assert _eMatrix.element[i][i] == _eMatrix.NOT_IN_USE;
            }
        }
        
        modularity /= 2*_numEdges;
        return modularity;
    }
    
    /**
     * @param e the increase in modularity due to merging the communities at the ends of this edge is returned
     * @return the increase in modularity due to merging the communities at the ends of the edge given as a parameter is returned
     */
    public double getModularityIncrease(Edge e)
    {
        //get the modularit increase if we merge the communities at the ends of the edge e
        //It is 2(e_ij − a_i*a_j )
        int i = e.firstEnd, j = e.secondEnd;
        
        double temp = ((double)_aArray[i]*_aArray[j])/((double)2*_numEdges);
        double increase = 2*((double)_eMatrix.element[i][j] - temp);
        increase /= 2*_numEdges;
        
        return increase;
    }
    
    /**
     * @return the number of communities in the partition
     */
    public int getNumCommunities()
    {
        return _communityCollection.getNumCommunities();
    }
    
}
